/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *          
 * Date:    Jan. 2011
 */

#ifndef __CPU_EDGE_PIECEWISE_PRED_HH__
#define __CPU_EDGE_PIECEWISE_PRED_HH__

#include <vector>
#include <deque>

#include "base/types.hh"
#include "base/trace.hh"
#include "config/the_isa.hh"
#include "arch/isa_traits.hh"
#include "cpu/edge/pred/base_binary_predictor.hh"
#include "params/DerivEdgeCPU.hh"

class DerivEdgeCPUParams;

/**
 * A piece-wise predictor for branch type prediction or behave like a
 * component for exit id prediction.
 * */
template<class Impl>
class PiecewiseBP : public BaseBinaryPredictor<Impl>
{
  public:
    typedef TheISA::BlockID BlockID;
    typedef std::deque<Addr> PathHistory;

    /** This piecewise predictor has two modes. */
    enum PiecewiseMode{
        Unknown,
        SingleBitHistory, /// Just allow single-bit history to be recorded each time
        ExitHistory, /// History representing the exit id of a hyperblock is allowed
        TypeHistory  /// History representing the branch type of a hyperblock is allowed
    };

    /** Local future file entry. */
    struct LFFEntry {
        unsigned index; // Index to the weight table.
	unsigned history; // History of this entry. 
    };

    /** The constructor. */
    PiecewiseBP(DerivEdgeCPUParams *params);
    PiecewiseBP(int history_bits, int local_history_bits, int path_table_size,
            int table_size, int local_history_table_size,
            unsigned weight_bits, unsigned block_shift_amt);

    /** The destructor. */
    ~PiecewiseBP();

    /** Initialize variables of this predictor. */
    void initVars();

    /** Initialize this predictor. */
    void initMode(PiecewiseMode init_mode);

    /** Reset this predictor. */
    void reset();

    /** Lookup the predictor to produce a prediction. */
    bool lookup(BlockID block_id, BlockID oldest_block_id, Addr block_pc,
            ThreadID tid);

    /** Non-speculative update the weight tables. */
    bool update(BlockID block_id, Addr block_pc, ThreadID tid,
            bool prediction, bool mispredicted);

    /** Update local history table. */
    void updateLocalHistoryTable(BlockID block_id, Addr block_pc,
            TheISA::ExitID exit_id, ThreadID tid);

    /** Update local history table. */
    void updateLocalHistoryTable(BlockID block_id, Addr block_pc,
            TheISA::BTypeID type_id, ThreadID tid);

    /** Speculatively update the table using exit id. */
    void speculativeUpdate(Addr new_pc, BlockID block_id,
            TheISA::ExitID exit_id, ThreadID tid);

    /** Speculatively update the table using branch type id. */
    void speculativeUpdate(Addr new_pc, BlockID block_id,
            TheISA::BTypeID type_id, ThreadID tid);

    /** Squash due to various reasons. */
    void squash(BlockID block_id, ThreadID tid);

    /** Squash due to misprediction. */
    void squash(Addr block_pc, BlockID block_id, bool prediction, ThreadID tid);

    /** Squash due to misprediction in exit id history mode. */
    void squash(Addr block_pc, BlockID block_id, TheISA::ExitID exit_id,
            ThreadID tid);

    /** Squash due to misprediction in branch type id history mode. */
    void squash(Addr block_pc, BlockID block_id, TheISA::BTypeID type_id,
            ThreadID tid);

    /** Get the global history to a specific frame. */
    uint64_t getGlobalHistory(BlockID block_id, ThreadID tid);

    /** Get the path history to a specific frame. */
    uint64_t getPathHistory(BlockID block_id, ThreadID tid);

  private:
    /** Mode of this predictor. */
    PiecewiseMode mode;

    /**
     * Each entry in the table is an array of integers which
     * represent the weights of a perceptron.
     * */
    typedef std::vector<int> WeightTableEntry;

    /**
     * The two-dimension version of the weight table, consisting
     * with an array of the one-dimension table entry.
     * */
    typedef std::vector<WeightTableEntry*> TwoDimWeightTable;

    /**
     * The three-dimension weight table, consisting of an array of
     * the two-dimension weight table.
     * */
    std::vector<TwoDimWeightTable*> weightTable;

    /** Histories of all threads, speculatively updated. */
    uint64_t historyTable[Impl::MaxThreads];

    /** Path histories of all threads, speculatively updated. */
    PathHistory pathHistoryTable[Impl::MaxThreads];

    /** Histories of all in-flight blocks. */
    uint64_t historyFile[Impl::MaxInFlightBlockNum];

    /** Path histories of all in-flight blocks. */
    PathHistory pathHistoryFile[Impl::MaxInFlightBlockNum];

    /**
     * The number of bits of history. This is the size of third
     * dimension of the weight table.
     * */
    int historyBits;

    /** Local history bits. */
    int localHistoryBits;

    /**
     * The number of entries of the second dimension. This is indexed
     * by the path-based address of previously executed block.
     * */
    int pathTableSize;

    /**
     * The number of entries of the third dimension. This is indexed
     * by PC of the currently predicting block.
     * */
    int tableSize;

    /** Local history table size. */
    int localHistoryTableSize;

    /** The mask of the history. */
    uint64_t historyMask;

    /** The mask of the path address. */
    uint64_t pathAddrMask;

    /** The mask of PC used to index the first dimension of the table. */
    uint64_t indexPCMask;

    /** The number of bits of each weight. */
    unsigned weightBits;

    /** The maximum value of weight. */
    int maxWeight;

    /** The minimum value of weight. */
    int minWeight;

    /** Record the sum of lookup of each inflight block. */
    double sumTable[Impl::MaxInFlightBlockNum];

    /** The number of bits to align. */
    unsigned blockShiftAmt;

    /** The number of bits to alloy exit id with path addr. */
    int exitIdBits;

    /** The number of bits to alloy type id with path addr. */
    int typeIdBits;

    /** Threshold for training the perceptron. */
    double threshold;

    /** Array of local future file. */
    LFFEntry localFutureFile[Impl::MaxInFlightBlockNum];

    /**
     * The two-dimension version of the local weight table
     * */
    std::vector<WeightTableEntry*> localWeightTable;

    /** History table of local histories. */
    std::vector<uint64_t> localHistoryTable;

    /** Local history of this lookup. This is a speculative history. */
    uint64_t currentLocalHistory[Impl::MaxThreads];

    /** Local history mask. */
    uint64_t localHistoryMask;

    /** Local history table mask. */
    uint64_t localHistoryTableMask;

    /** Lookup the weight table, generating the prediction. */
    bool predictorLookup(BlockID block_id, Addr block_pc, ThreadID tid);

    /** Non-speculative update the weight table. */
    void updateWeightTable(BlockID block_id, Addr block_pc,
            bool prediction, ThreadID tid);

    /** Speculatively update the table using single bit history. */
    void speculativeUpdate(Addr new_pc, BlockID block_id,
            bool prediction, ThreadID tid);

    /** Update history using single bit history. */
    uint64_t updateHistory(uint64_t history, bool prediction, bool is_global);

    /** Update history using exit id. */
    uint64_t updateHistory(uint64_t history, TheISA::ExitID exit_id,
            bool is_global);

    /** Update history using branch type id. */
    uint64_t updateHistory(uint64_t history, TheISA::BTypeID type_id,
            bool is_global);

    /** Update path history using single bit history. */
    void updatePathHistory(PathHistory &path_history, Addr new_pc);

    /** Update path history using exit id. */
    void updatePathHistory(PathHistory &path_history, Addr new_pc,
            TheISA::ExitID exit_id);

    /** Update path history using branch type id. */
    void updatePathHistory(PathHistory &path_history, Addr new_pc,
            TheISA::BTypeID type_id);

    /** Update local history table. */
    void updateLocalHistoryTable(BlockID block_id, Addr block_pc,
            bool prediction, ThreadID tid);

    /** Get local history. */
    uint64_t getSpeculativeLocalHistory(BlockID block_id,
            BlockID oldest_block_id, Addr block_pc, ThreadID tid);

    /** Find a value in the table. */
    inline double lookupTable(int table_idx, int path_idx, int history_idx,
            bool is_global)
    {
        assert(table_idx < tableSize);

        if (is_global) {

            assert(path_idx < pathTableSize + 1);
            assert(history_idx < historyBits);

            DPRINTF(BPDEBUG, "global weight:%i\n",
                    (*((*(weightTable[table_idx]))[path_idx]))[history_idx]);

            return (double) (*((*(weightTable[table_idx]))[path_idx]))[history_idx];

        } else {
            assert(path_idx == 0);
            assert(history_idx < localHistoryBits);

            DPRINTF(BPDEBUG, "local weight:%i\n",
                    (*(localWeightTable[table_idx]))[history_idx]);

            return (*(localWeightTable[table_idx]))[history_idx];

        }
    }

    /** Find a value in the table. */
    inline void incWeight(int table_idx, int path_idx, int history_idx,
            bool is_global)
    {
        assert(table_idx < tableSize);

        if (is_global) {
            assert(path_idx < pathTableSize + 1);
            assert(history_idx < historyBits);

            (*((*(weightTable[table_idx]))[path_idx]))[history_idx]++;

            DPRINTF(BPDEBUG, "Increase the global table, get a weight %i\n",
                    (*((*(weightTable[table_idx]))[path_idx]))[history_idx]);
        } else {
            assert(path_idx == 0);
            assert(history_idx < localHistoryBits);

            (*(localWeightTable[table_idx]))[history_idx]++;

            DPRINTF(BPDEBUG, "Increase the local table, get a weight %i\n",
                    (*(localWeightTable[table_idx]))[history_idx]);
        }
    }

    /** Find a value in the table. */
    inline void decWeight(int table_idx, int path_idx, int history_idx,
            bool is_global)
    {
        assert(table_idx < tableSize);

        if (is_global) {
            assert(path_idx < pathTableSize + 1);
            assert(history_idx < historyBits);

            (*((*(weightTable[table_idx]))[path_idx]))[history_idx]--;

            DPRINTF(BPDEBUG, "Decrease the table, get a weight %i\n",
                    (*((*(weightTable[table_idx]))[path_idx]))[history_idx]);
        } else {
            assert(path_idx == 0);
            assert(history_idx < localHistoryBits);

            (*(localWeightTable[table_idx]))[history_idx]--;
        }
    }
};

#endif // __CPU_EDGE_PIECEWISE_PRED_HH__
